import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {
    public int subarraySum(int[] nums, int k) {
        // key-前缀和  value-前缀和出现的次数
        // dp[i]：表示 [0, i] 区间所有元素的和
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1); // 前缀和为 0 的出现过 1 次

        int dp = 0;
        int ret = 0;

        for(int x : nums) {
            dp += x; // 计算当前位置的前缀和
            ret += hash.getOrDefault(dp - k, 0); // dp - k 出现的次数
            hash.put(dp, hash.getOrDefault(dp, 0) + 1);
        }

        return ret;
    }
}
